"""
221. 最大正方形 - 算法测试框架

用于测试算法的正确性和性能
"""

import time
import sys
from typing import List, Tuple
from alg import Solution
from gen import TestDataGenerator, analyze_matrix_properties

class AlgorithmTester:
    """算法测试器"""
    
    def __init__(self):
        self.solution = Solution()
        self.generator = TestDataGenerator()
    
    def brute_force_solution(self, matrix: List[List[str]]) -> int:
        """暴力解法用于验证正确性"""
        if not matrix or not matrix[0]:
            return 0
        
        rows, cols = len(matrix), len(matrix[0])
        max_side = 0
        
        # 枚举所有可能的左上角
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == "1":
                    # 枚举正方形边长
                    max_possible_side = min(rows - i, cols - j)
                    for side in range(1, max_possible_side + 1):
                        # 检查是否为全1正方形
                        is_valid = True
                        for r in range(i, i + side):
                            for c in range(j, j + side):
                                if matrix[r][c] != "1":
                                    is_valid = False
                                    break
                            if not is_valid:
                                break
                        
                        if is_valid:
                            max_side = max(max_side, side)
                        else:
                            break
        
        return max_side * max_side
    
    def test_correctness(self) -> bool:
        """测试算法正确性"""
        print("=" * 60)
        print("算法正确性测试")
        print("=" * 60)
        
        all_passed = True
        test_cases = self.generator.generate_all_test_cases()
        
        for i, (name, matrix) in enumerate(test_cases[:15], 1):  # 只测试前15个用例
            print(f"\n测试用例 {i}: {name}")
            
            # 打印矩阵（如果不太大）
            if len(matrix) <= 5 and (not matrix or len(matrix[0]) <= 10):
                print("输入矩阵:")
                for row in matrix:
                    print(" ".join(row))
            else:
                print(f"矩阵维度: {len(matrix)}x{len(matrix[0]) if matrix else 0}")
            
            try:
                # 位运算方法
                start_time = time.time()
                result1 = self.solution.maximalSquare(matrix)
                bitwise_time = time.time() - start_time
                
                # 暴力验证方法（只对小矩阵使用）
                if len(matrix) <= 10 and (not matrix or len(matrix[0]) <= 10):
                    start_time = time.time()
                    result2 = self.brute_force_solution(matrix)
                    brute_force_time = time.time() - start_time
                    
                    is_same = result1 == result2
                    all_passed = all_passed and is_same
                    
                    print(f"位运算方法结果: {result1}")
                    print(f"暴力验证结果: {result2}")
                    print(f"结果一致: {'✓' if is_same else '✗'}")
                    print(f"位运算法用时: {bitwise_time:.6f}s")
                    print(f"暴力法用时: {brute_force_time:.6f}s")
                    
                    if not is_same:
                        print("❌ 测试失败！")
                        return False
                else:
                    print(f"位运算方法结果: {result1}")
                    print(f"位运算法用时: {bitwise_time:.6f}s")
                    print("(矩阵过大，跳过暴力验证)")
                    
            except Exception as e:
                print(f"❌ 测试出错: {e}")
                all_passed = False
        
        print(f"\n{'✅ 所有测试通过！' if all_passed else '❌ 部分测试失败'}")
        return all_passed
    
    def test_performance(self):
        """性能测试"""
        print("\n" + "=" * 60)
        print("算法性能测试")
        print("=" * 60)
        
        # 性能测试用例
        performance_cases = [
            ("小矩阵5x5", self.generator.generate_matrix(5, 5, 0.6)),
            ("中等矩阵15x15", self.generator.generate_matrix(15, 15, 0.6)),
            ("大矩阵30x30", self.generator.generate_matrix(30, 30, 0.6)),
            ("高密度10x10", self.generator.generate_matrix(10, 10, 0.9)),
            ("低密度10x10", self.generator.generate_matrix(10, 10, 0.1)),
        ]
        
        print(f"{'测试用例':<15} {'矩阵大小':<10} {'1的密度':<8} {'执行时间(s)':<12} {'结果':<8}")
        print("-" * 65)
        
        for name, matrix in performance_cases:
            props = analyze_matrix_properties(matrix)
            
            start_time = time.time()
            result = self.solution.maximalSquare(matrix)
            execution_time = time.time() - start_time
            
            print(f"{name:<15} {props['rows']}x{props['cols']:<7} {props['ones_density']:<8.2f} {execution_time:<12.6f} {result:<8}")
    
    def test_special_cases(self):
        """测试特殊用例"""
        print("\n" + "=" * 60)
        print("特殊用例测试")
        print("=" * 60)
        
        special_cases = [
            ("空矩阵", []),
            ("单行空", [[]]),
            ("单个0", [["0"]]),
            ("单个1", [["1"]]),
            ("全0矩阵", [["0","0"],["0","0"]]),
            ("全1矩阵", [["1","1"],["1","1"]]),
            ("单行", [["1","0","1","1"]]),
            ("单列", [["1"],["0"],["1"],["1"]]),
        ]
        
        for name, matrix in special_cases:
            print(f"\n{name}:")
            if matrix and matrix[0]:
                print("矩阵:")
                for row in matrix:
                    print(" ".join(row))
            else:
                print("空矩阵")
            
            try:
                result = self.solution.maximalSquare(matrix)
                print(f"结果: {result}")
                
                # 分析结果合理性
                if matrix and matrix[0]:
                    props = analyze_matrix_properties(matrix)
                    max_possible_area = min(props['rows'], props['cols']) ** 2
                    if result <= max_possible_area:
                        print(f"结果合理 ✓ (最大可能面积: {max_possible_area})")
                    else:
                        print(f"结果异常 ✗ (超过最大可能面积: {max_possible_area})")
                
            except Exception as e:
                print(f"测试出错: {e}")
    
    def verify_algorithm_logic(self):
        """验证算法逻辑"""
        print("\n" + "=" * 60)
        print("算法逻辑验证")
        print("=" * 60)
        
        # 创建已知结果的测试用例
        test_cases = [
            ("2x2正方形", [["1","1"],["1","1"]], 4),
            ("3x3正方形", [["1","1","1"],["1","1","1"],["1","1","1"]], 9),
            ("无正方形", [["1","0"],["0","1"]], 1),
            ("L型", [["1","0","0"],["1","0","0"],["1","1","1"]], 1),
        ]
        
        for name, matrix, expected in test_cases:
            print(f"\n{name} (期望结果: {expected}):")
            print("矩阵:")
            for row in matrix:
                print(" ".join(row))
            
            result = self.solution.maximalSquare(matrix)
            print(f"算法结果: {result}")
            print(f"验证: {'✓' if result == expected else '✗'}")
            
            if result != expected:
                print(f"❌ 期望 {expected}，得到 {result}")
    
    def analyze_bit_operations(self, matrix: List[List[str]]):
        """分析位运算过程"""
        print("\n位运算过程分析:")
        
        if not matrix:
            print("空矩阵")
            return
            
        # 转换为数字
        nums = [int(''.join(row), base=2) for row in matrix]
        print(f"二进制转换: {[bin(num) for num in nums]}")
        print(f"十进制表示: {nums}")
        
        n = len(nums)
        max_area = 0
        
        for i in range(n):
            temp = nums[i]
            print(f"\n从第{i}行开始:")
            for j in range(i, n):
                if j > i:
                    temp &= nums[j]
                    print(f"  与第{j}行相与: {bin(temp)} -> {temp}")
                
                w = self.solution.getWidth(temp)
                h = j - i + 1
                area = min(w, h) ** 2
                max_area = max(max_area, area)
                
                print(f"  高度={h}, 宽度={w}, 正方形边长={min(w,h)}, 面积={area}")
        
        print(f"\n最大面积: {max_area}")
    
    def test_with_analysis(self):
        """带分析的测试"""
        print("\n" + "=" * 60)
        print("算法分析测试")
        print("=" * 60)
        
        # 选择一个小矩阵进行详细分析
        matrix = [["1","0","1","1"],["1","1","1","1"],["1","0","1","1"]]
        print("示例矩阵:")
        for row in matrix:
            print(" ".join(row))
        
        result = self.solution.maximalSquare(matrix)
        print(f"\n算法结果: {result}")
        
        # 详细分析位运算过程
        self.analyze_bit_operations(matrix)
    
    def run_all_tests(self):
        """运行所有测试"""
        print("221. 最大正方形 - 完整测试套件")
        print("=" * 60)
        
        try:
            # 1. 正确性测试
            if not self.test_correctness():
                print("❌ 正确性测试失败，停止后续测试")
                return False
            
            # 2. 特殊用例测试
            self.test_special_cases()
            
            # 3. 算法逻辑验证
            self.verify_algorithm_logic()
            
            # 4. 算法分析
            self.test_with_analysis()
            
            # 5. 性能测试
            self.test_performance()
            
            print("\n" + "=" * 60)
            print("✅ 所有测试完成！")
            print("=" * 60)
            
            return True
            
        except Exception as e:
            print(f"❌ 测试过程中出错: {e}")
            return False

def main():
    """主测试函数"""
    tester = AlgorithmTester()
    
    print("选择测试模式:")
    print("1. 完整测试")
    print("2. 只测试正确性")
    print("3. 只测试性能")
    print("4. 只测试特殊用例")
    print("5. 算法分析测试")
    
    try:
        choice = input("请选择 (1-5): ").strip()
        
        if choice == "1":
            tester.run_all_tests()
        elif choice == "2":
            tester.test_correctness()
        elif choice == "3":
            tester.test_performance()
        elif choice == "4":
            tester.test_special_cases()
        elif choice == "5":
            tester.test_with_analysis()
        else:
            print("运行完整测试...")
            tester.run_all_tests()
            
    except KeyboardInterrupt:
        print("\n测试被用户中断")
    except Exception as e:
        print(f"测试出错: {e}")

if __name__ == "__main__":
    main()